1. Field of the Invention
This invention relates to a division circuit and more particularly to a division circuit for signed division
2. Description of the Prior Art
According to the prior art, when division on signed dividend and divisor expressed by a complement of 2 is carried out, in order to obtain an accurate quotient and remainder, if the dividend and/or divisor is negative, they are converted to positive values before the division. As a typical division algorithm, two examples of restoring type (pull-back method) and non-restoring type (pull-out method) will be described.
First, the conventional restoring type division algorithm will be explained referring to a structure of a division circuit shown in FIG. 1.
If a dividend of n bits is a and a divisor of m(n greater than m) bits is b in FIG. 1, a division circuit comprises a remainder register 101 of n bits for storing high order side of a partial remainder during division operation and storing the remainder at the time of division end, a dividend/quotient register 102 of n bits for storing a dividend at the time of division start and successively storing low order side of the partial remainder and a quotient during division operation, a divisor register 103 of n bits for storing the divisor, a subtractor 104 of n bits, a selector 105 in which data obtained by combining a content of the remainder register 101 with that of a dividend/quotient register 102 is shifted by 1 bit so that the highest bit is shifted out, and then, data P# of that high order n bits, namely, data obtained by combining low order nxe2x88x921 bits of the remainder register 101 with the highest bit of the dividend/quotient register 102 or output of the subtractor 104 is selected and supplied to the remainder register 101, and a control circuit 106 for determining a quotient by receiving division result of the subtractor 104 and selectively controlling the selector 105.
Next, the division operation using the division circuit having such a structure will be described according to its operation cycle.
First, if the dividend a and/or divisor b are negative, they/it are/is converted to positive numbers by taking complements thereof. If both are not negative, they are used as they are and these values are treated as a% and b% (first cycle, second cycle, action 1).
Next, the dividend a% is loaded on the dividend/quotient register 102 and then the divisor b% is loaded on the divisor register 103. 0 is loaded on all bits of the remainder register 101 (third cycle, action 2).
Then, the remainder register 101 and dividend register 102 are shifted by 1 bit to the left and high order n bit of data obtained by combining both the registers after the shift is assumed to be P# (fourth cycle, action 3-1). Then, the output data of the divisor register 103 is subtracted from data P# by means of the subtractor 104 (fourth cycle, action 3-2). Then, the content of the dividend/quotient register 102 is shifted by 1 bit to the left. When the output of the subtractor 104 is negative, 0 is written to the least significant bit of the dividend/quotient register 102 as a quotient. If the output of the subtractor 104 is not negative, 1 is written into the least significant bit of the dividend/quotient register 102 as a quotient (fourth cycle, action 3-3). Then, if the output of the subtractor 104 is not negative, the output of the subtractor 104 is stored in the remainder register 101, and when the output of the subtractor 104 is negative, data P# is stored in the remainder register 101 (pull-back method) (fourth cycle, action 3-4).
The actions (3-1)-(3-4) of aforementioned fourth cycle is repeated further (nxe2x88x921) times (fifth cyclexe2x80x94(n+3) cycle).
Next, if the sign of the dividend is the same as the sign of the divisor, the output of the dividend/quotient register 102 is stored in the dividend/quotient register 102 as a quotient. On the other hand, if the sign of the dividend is different from the sign of the divisor, a complement of the output of the dividend/quotient register 102 is taken and written back to the dividend/quotient register 102 ((n+4) cycle, action 5).
Next, when the dividend is not negative, the output of the remainder register 101 is stored as a remainder. On the other hand, when the dividend is negative, a complement of the output of the remainder register 101 is taken and written to the remainder register 101 ((n+5) cycle, action 6).
Finally, the quotient is stored in the dividend/quotient register 102 and the remainder is stored in the remainder register 101, and then the signed division is terminated ((n+6) cycle, action 7).
The division processing is carried out as described above. FIG. 2 shows an example of division in which dividend a=1001(binary) (means xe2x88x927 according to decimal notation) and divisor bxe2x88x920011 (binary) (means 3 according to decimal notation). In FIG. 2, the content of the remainder register 101 is expressed by P, the content of the dividend/quotient register 102 is expressed by A and the content of the divisor register 103 is expressed by B.
Then, the conventional non-restoring type division algorithm will be described with reference to a structure of the division circuit shown in FIG. 3.
In the aforementioned conventional non-restoring type division, if the partial remainder is negative, a temporarily subtracted divisor is pulled back and added, so that the partial remainder is returned to a positive number. However, considering a level lower by a digit, subtraction of the divisor is regarded as (remainder+divisor)xc3x972xe2x88x92divisor. Then, because (remainder+divisor)xc3x972xe2x88x92divisor is remainderxc3x972+divisor, when the partial remainder is negative, it is possible to store the partial remainder as it is and shift it by a bit to the left and then carry out addition instead of subtraction of the partial remainder and divisor. This method can reduce operation time per cycle as compared to the restoring type division. The non-restoring type division algorithm uses such a method.
If a dividend of n bits is a and a divisor of m(n greater than m) bits is b in FIG. 3, a division circuit comprises a remainder register 111 of n bits for storing high order side of a partial remainder during division operation and storing the remainder at the time of division end, a dividend/quotient register 112 of n bits for storing a dividend at the time of division start and successively storing low order side of the partial remainder and a quotient during division operation, a divisor register 113 of n bits for storing the divisor, an adder/subtractor 114 of n bits, and a control circuit 115 for determining a quotient by receiving operation result of the adder/subtractor 114 and instructing the adder/subtractor 114 to carry out addition or subtraction according to operation result of the adder/subtractor 114.
Next, the division operation using the division circuit having such a structure will be described according to its operation cycle.
First, if the dividend a and/or divisor b are negative, they/it are/is converted to positive numbers by taking complements thereof. If both are not negative, they are used as they are and these values are treated as a% and b% (first cycle, second cycle, action 1).
Next, the dividend a% is loaded on the dividend/quotient register 112 and then the divisor b% is loaded on the divisor register 113. 0 is loaded on all bits of the remainder register 111 (third cycle, action 2).
Then, the remainder register 111 and dividend register 112 are shifted by 1 bit to the left and high order n bit of data obtained by combining both the registers after the shift is assumed to be P% (fourth cycle, action 3-1). Then, the output data of the divisor register 113 is subtracted from data P# by means of the subtractor 114 (fourth cycle, action 3-2). Then, the content of the dividend/quotient register 112 is shifted by 1 bit to the left. As for a value to be stored in the least significant bit of the dividend/quotient 112, when the output of the adder/subtractor 114 is negative, 0 is written into the least significant bit of the dividend/quotient register 112 as a quotient. If the output of the adder/subtractor 114 is not negative, 1 is written into the least significant bit of the dividend/quotient register 112 (fourth cycle, action 3-3). Subsequently, the output of the adder/subtractor 114 is stored in the remainder register 111 (fourth cycle, action 3-4).
In a next cycle, if the output of the remainder register 111 is negative, the remainder register 111 and dividend/quotient register 112 are shifted by a bit to the left. Then, data P# of high order n bits of data in which the contents of both the registers are combined after the shift and the output of the divisor register 113 are summed up by the adder/subtractor 114. On the other hand, if the output of the remainder register is not negative, the remainder register 111 and dividend/quotient register 112 are shifted by a bit to the left. Then, the output of the divisor register 113 is subtracted from data P# of high order n bits in which the contents of both the registers are combined after the shift by means of the adder/subtractor 114 (fifth cycle, action 4-1). Then, the content of the dividend/quotient register 112 is shifted by a bit to the left. When the output of the adder/subtractor 114 is negative, 0 is written into the least significant bit of the dividend/quotient register 112 as a quotient. If the output of the adder/subtractor is not negative, 1 is written therein as a quotient (fifth cycle, action 4-2). Then, the output of the adder/subtractor 114 is stored in the remainder register 111 (fifth cycle, action 4-3).
Next, the aforementioned action (4-1)xcx9c(4-3) of the fifth cycle is repeated further (nxe2x88x922) times (sixth cyclexe2x80x94(n+3) cycle).
If the output of the remainder register 111 is not negative, the remainder register 111 holds the value as it does. On the other hand, if the output of the remainder register 111 is negative, the output of the remainder register 111 and output of the divisor register 113 are summed up by means of the adder/subtractor 114 and its result is stored in the remainder register 111 ((n+4) cycle, action 6).
Next, if the sign of the dividend is the same as the sign of the divisor, the output of the dividend/quotient register 112 is stored in the dividend/quotient register 112. If the sign of the dividend is different from the sign of the divisor, a complement of the output of the dividend/quotient register 112 is taken and written back to the dividend/quotient register 112 ((n+5) cycle, action 7).
If the dividend is not negative, the output of the remainder register 111 is held. If the dividend is negative, a complement of the output of the remainder register 111 is taken and written back to the remainder register 111 ((n+6) cycle, action 8).
Finally, the quotient is stored in the dividend/quotient register 112 and the remainder is stored in the remainder register 111, and then the signed division is terminated ((n+7) cycle, action 9).
The division processing is carried out as described above. FIG. 4 shows an example of division in which dividend a=1001 (binary) (means xe2x88x927 according to decimal notation) and divisor b=0011 (binary) (means 3 according to decimal notation) like the aforementioned conventional example. In FIG. 4, the content of the remainder register 111 is expressed by P, the content of the dividend/quotient register 112 is expressed by A and the content of the divisor register 113 is expressed by B.
As described above, when it is intended to obtain a quotient and remainder accurately in division operation of the signed dividend and divisor, if the dividend and/or divisor is negative, by taking a complement of 2, the negative values are converted to positive values and the division is carried out with positive dividend and divisor. Thus, if both the dividend and divisor are negative, a complement of 2 must be taken for both the values. Thus, a time for taking a complement is added to division time so that the division time is extended, which is disadvantage of the prior art. Further, if the dividend is negative, a complement of 2 of a reminder also must be taken to be corrected, thereby further increasing the division time.
Accordingly, the present invention has been achieved in order to solve the above problem, and it is an object of the invention to provide a division circuit capable of obtaining accurate quotient and remainder by carrying out signed division without converting to positive values even if the dividend and/or divisor is negative.
To achieve the above object, there is provided a division circuit comprising: a divisor register for storing a divisor: a dividend register for storing a dividend at the time of division start and shifting a stored value therein by predetermined bits and holding during division operation; an adder/subtractor for carrying out addition and subtraction; a remainder register for storing an output of the adder/subtractor during the division operation and storing a remainder at the time of division termination; a quotient register for storing a quotient; a selector for selecting a combined value obtained by combining high order predetermined bits of a content stored in the dividend register with predetermined bits of a content stored in the remainder register or a result of operation of the adder/subtractor, and then outputting to the remainder register; an all zero detector for determining whether or not a partial remainder is 0; a first comparator for comparing the sign of the dividend to the sign of the divisor; a second comparator for comparing the sign of operation result of the adder/subtractor to the sign of the dividend; and a control circuit for determining the quotient based on determination result of the all zero detector and comparison result of the second comparator so as to control selection of the selector, the adder/subtractor carrying out addition or subtraction for the combined value and the divisor according to comparison result of the first comparator, the control circuit determining the quotient based on the comparison result of the second comparator and the determination result of the all zero detector, the selector selecting the combined value or the operation result of the adder/subtractor according to the quotient and outputting to the remainder register, the dividend register repeating operation for shifting a stored value therein by predetermined bits and then storing by a predetermined frequency, the quotient register for, when the sign of the dividend is different from the sign of the divisor, obtaining a complement of a stored value therein and storing the complement therein.
According to a preferred embodiment of the present invention, the adder/subtractor, when the sign of the dividend is the same as the sign of the divisor according to the comparison result of the first comparator, subtracts the divisor from the combined value, and when the sign of the dividend is different from the sign of the divisor according to the comparison result of the first comparator, sums up the combined value and the divisor.
According to another preferred embodiment of the present invention, the control circuit, when the sign of output of the adder/subtractor is the same as the sign of the dividend according to the comparison result of the second comparator, writes 1 into the least significant level of the quotient register as the quotient, when the sign of output of the adder/subtractor is different from the sign of the dividend according to the comparison result of the second comparator and the partial remainder is 0 according to the determination result of the all zero detector, writes 1 into the least significant level of the quotient register as the quotient, and when the sign of output of the adder/subtractor is different from the sign of the dividend according to the comparison result of the second comparator and the partial remainder is not 0 according to the determination result of the all zero detector, writes 0 into the least significant level of the quotient register as the quotient.
According to still another preferred embodiment of the present invention, the dividend register and the quotient register are the same shared register and during division operation, predetermined bits of a value stored in the shared register are successively shifted to high order by predetermined bits each while the quotient being stored successively from low order of the shared register.
According to further embodiment of the present invention, both signed division and unsigned division are carried out by extending 0 to upper sides of the dividend and the divisor when the unsigned division is carried out, and by extending sign bits over the dividend and the divisor when the signed division is carried out.
Further to achieve the above object, there is provided a division circuit comprising: a divisor register for storing a divisor; a dividend register for storing a dividend at the time of division start and shifting a stored value therein by predetermined bits and holding during division operation; an adder/subtractor for carrying out addition and subtraction; a remainder register for storing an output of the adder/subtractor during the division operation and storing a remainder at the time of division termination; a quotient register for storing a quotient; an all zero detector for determining whether or not a temporary partial remainder is 0; a first comparator for comparing the sign of the dividend with the sign of the divisor; a second comparator for comparing the sign of operation result of the adder/subtractor with the sign of the dividend; and a control circuit for determining the quotient based on determination result of the all zero detector and comparison results of the first comparator and the second comparator and then instructing the adder/subtractor to carry out addition or subtraction of a next cycle according to the quotient and the comparison result of the first comparator, the adder/subtractor carrying out addition or subtraction about the divisor and a combined value obtained by combining high order predetermined bits of a content stored in the dividend register with predetermined bits of a content stored in the remainder register according to the comparison result of the first comparator, the control circuit determining the quotient based on the comparison result of the second comparator and the determination result of the all zero detector and storing operation result of addition or subtraction by the adder/subtractor in the remainder register, the control circuit repeating operation for carrying out addition or subtraction by the adder/subtractor with respect to the combined value of the next cycle and the divisor according to an instruction of the control circuit based on the quotient obtained at a previous cycle, operation for determining a quotient in the same manner as the determination of the quotient according to operation result of the addition or subtraction, operation for shifting a value of the dividend register by predetermined bits and storing, and operation for storing operation result of the adder/subtractor in the remainder register, by a predetermined frequency, the remainder register correcting a stored value therein according to the quotient obtained at the previous cycle and storing the corrected value therein, the quotient register, when the sign of the dividend is different from the sign of the divisor, obtaining a complement of the stored value and storing the complement therein.
The nature, principle and utility of the invention will become more apparent from the following detailed description when read in conjunction with the accompanying drawings.